package lc;

import java.util.LinkedList;
import java.util.Queue;

public class lc542 {
    public static void main(String[] args) {
        updateMatrix(new int[][]{{0,0,0}, {0,1,0}, {1,1,1}});
    }
    public static int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(mat[i][j] == 0) queue.add(new int[]{i, j});
                else mat[i][j] = -1;
            }
        }

        while(!queue.isEmpty()){
            int[] arr = queue.poll();
            int i = arr[0], j = arr[1];
            if(i > 0 && mat[i - 1][j] == -1){
                mat[i - 1][j] = mat[i][j] + 1;
                queue.add(new int[]{i - 1, j});
            }
            if(i < m - 1 && mat[i + 1][j] == -1){
                mat[i + 1][j] = mat[i][j] + 1;
                queue.add(new int[]{i + 1, j});
            }
            if(j > 0 && mat[i][j - 1] == -1){
                mat[i][j - 1] = mat[i][j] + 1;
                queue.add(new int[]{i, j - 1});
            }
            if(j < n - 1 && mat[i][j + 1] == -1){
                mat[i][j + 1] = mat[i][j] + 1;
                queue.add(new int[]{i, j + 1});
            }
        }
        return mat;
    }
}
